package basic.study.algorithms.sort;

/**
 * @author Kevin
 * @date 2020/2/13 23:59
 */
public class HeapSort2 {
    public static void main(String[] args) {
        int[] nums = {3,2,1,5,6,4};
        System.out.println(findKthLargest(nums, 2));
    }


    public static int findKthLargest(int[] nums, int k) {
        buildHeap(nums, k);

        for(int i = k; i < nums.length; i++) {
            if(nums[i] < nums[0]) continue;
            swap(nums, i, 0);
            heapify(nums, k, 0);
        }
        return nums[0];
    }

    public static void buildHeap(int[] arr, int k) {
        //从最后一个非叶子节点开始遍历，进行小顶堆的堆化排序
        for (int i = (k-1)/2; i>= 0; i--) {
            heapify(arr, k, i);
        }
    }

    public static void heapify(int[] arr, int k, int i) {
        int minPos = i;
        while(true) {
            if (2 * i + 1 < k && arr[2 * i + 1] < arr[i]) minPos = 2 * i + 1;
            if (2 * i + 2 < k && arr[2 * i + 2] < arr[minPos]) minPos = 2 * i + 2;
            if (minPos == i) break;
            //若子节点比父节点小，进行交换
            swap(arr, i, minPos);
            i = minPos;
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
